{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "file_path = 'Data.txt'\n",
    "out_path = 'block_result.txt'\n",
    "\n",
    "# 打开并读取文件\n",
    "with open(file_path, 'r') as f:\n",
    "    lines = f.readlines()\n",
    "\n",
    "# 初始化两个空列表\n",
    "from_nodes = []\n",
    "to_nodes = []\n",
    "degree = []\n",
    "max_node_id = 0\n",
    "max_to_id = 0\n",
    "\n",
    "matrixs = {}\n",
    "group_nodes = 100\n",
    "\n",
    "# 遍历每一行\n",
    "for line in lines:\n",
    "    # 分割行并将结果添加到列表中\n",
    "    from_node_id, to_node_id = map(int, line.split())\n",
    "\n",
    "    group = (to_node_id - 1) // group_nodes #计算出所属的组 \n",
    "\n",
    "    if group not in matrixs:  #如果matrixs中没有这个组，就创建一个\n",
    "        matrixs[group] = {}\n",
    "        matrixs[group][from_node_id - 1] = [to_node_id - 1]\n",
    "    else:\n",
    "        if from_node_id - 1 not in matrixs[group]: #如果这个组中没有这个节点，创建该节点\n",
    "            matrixs[group][from_node_id - 1] = [to_node_id - 1]\n",
    "        else:\n",
    "            matrixs[group][from_node_id - 1].append(to_node_id - 1) #如果这个组中有这个节点，添加到该节点的列表中\n",
    "\n",
    "    if(from_node_id > max_node_id):\n",
    "        for i in range(max_node_id, from_node_id ):\n",
    "            degree.append(0)\n",
    "        max_node_id = from_node_id\n",
    "    \n",
    "    if(to_node_id > max_to_id):\n",
    "        max_to_id = to_node_id\n",
    "        \n",
    "    degree[from_node_id - 1] += 1 #计算出度\n",
    "\n",
    "    from_nodes.append(from_node_id - 1)\n",
    "    to_nodes.append(to_node_id - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "node_nums = max(max_node_id, max_to_id) \n",
    "group_nums = node_nums // group_nodes + 1 #计算组数\n",
    "degree = np.array(degree)\n",
    "dead_ends = np.where(degree == 0)[0]    #找出度为0的节点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "diff: 9.0494184383289e-05\n"
     ]
    }
   ],
   "source": [
    "from IPython.display import clear_output\n",
    "\n",
    "rank_old = np.ones(node_nums) / node_nums\n",
    "d = 0.85\n",
    "epsilon = 1e-8\n",
    "\n",
    "while True:\n",
    "    rank_new = np.ones(node_nums) * (1 - d) / node_nums\n",
    "\n",
    "    rank_new += d * np.sum(rank_old[dead_ends]) / node_nums  #先处理所有dead_end节点\n",
    "\n",
    "    for group, matrix in matrixs.items():   #对每个分块矩阵进行迭代计算\n",
    "        group_start = group * group_nodes\n",
    "        group_end = (group + 1) * group_nodes  if (group + 1) * group_nodes < node_nums else node_nums\n",
    "\n",
    "        for from_node, to_nodes in matrix.items():  #该分块矩阵中的每一列\n",
    "            for to_node in to_nodes:\n",
    "                rank_new[to_node] += d * rank_old[from_node] / degree[from_node] #更新rank值\n",
    "                     \n",
    "    diff = np.sum(np.abs(rank_new - rank_old))\n",
    "    if diff < node_nums * epsilon:\n",
    "        break\n",
    "    \n",
    "    clear_output(wait=True)\n",
    "    print(f\"diff: {diff}\")\n",
    "    \n",
    "    rank_old = rank_new\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Index: 2730, Value: 0.000871413785939628\n",
      "Index: 7102, Value: 0.000854093577444934\n",
      "Index: 1010, Value: 0.0008491780767153843\n",
      "Index: 368, Value: 0.000835473026857167\n",
      "Index: 1907, Value: 0.000830166144751815\n",
      "Index: 7453, Value: 0.0008202343300680922\n",
      "Index: 4583, Value: 0.0008174658880004726\n",
      "Index: 7420, Value: 0.000809918563420256\n",
      "Index: 1847, Value: 0.000809591030147981\n",
      "Index: 5369, Value: 0.0008055925435601312\n",
      "Index: 3164, Value: 0.0008046822790861687\n",
      "Index: 7446, Value: 0.0008027497128716406\n",
      "Index: 3947, Value: 0.0008018181860008152\n",
      "Index: 2794, Value: 0.0007919193649553848\n",
      "Index: 3215, Value: 0.0007817767134876383\n",
      "Index: 5346, Value: 0.0007808069646938417\n",
      "Index: 7223, Value: 0.0007769753201734474\n",
      "Index: 630, Value: 0.0007739891892213759\n",
      "Index: 4417, Value: 0.0007684350755836877\n",
      "Index: 4955, Value: 0.0007604058261171743\n",
      "Index: 3208, Value: 0.0007586423700990548\n",
      "Index: 2902, Value: 0.0007571633605248539\n",
      "Index: 5671, Value: 0.0007554744486563802\n",
      "Index: 5833, Value: 0.0007512886334094231\n",
      "Index: 5553, Value: 0.0007475833198907551\n",
      "Index: 8096, Value: 0.0007470304438100204\n",
      "Index: 3204, Value: 0.0007453961304891344\n",
      "Index: 758, Value: 0.0007445711657445823\n",
      "Index: 6301, Value: 0.000744210005331788\n",
      "Index: 5769, Value: 0.00074079690024291\n",
      "Index: 8194, Value: 0.0007397325222336754\n",
      "Index: 4957, Value: 0.0007376708913285218\n",
      "Index: 8060, Value: 0.00073600862187177\n",
      "Index: 7938, Value: 0.0007334811572109563\n",
      "Index: 5584, Value: 0.0007327724858574149\n",
      "Index: 6568, Value: 0.0007323065133683282\n",
      "Index: 1430, Value: 0.0007321843677065387\n",
      "Index: 7250, Value: 0.0007309834032379421\n",
      "Index: 3185, Value: 0.0007301226485545055\n",
      "Index: 2737, Value: 0.0007259002503408864\n",
      "Index: 3751, Value: 0.0007254722175346038\n",
      "Index: 150, Value: 0.0007254623218068504\n",
      "Index: 5099, Value: 0.0007208780033082646\n",
      "Index: 2944, Value: 0.0007170090200009661\n",
      "Index: 7872, Value: 0.0007150769526537926\n",
      "Index: 2639, Value: 0.0007136358713756498\n",
      "Index: 5074, Value: 0.0007136121318378156\n",
      "Index: 1034, Value: 0.0007126608885350507\n",
      "Index: 229, Value: 0.0007120146850260536\n",
      "Index: 6648, Value: 0.000711666689072726\n",
      "Index: 4222, Value: 0.00070989488895173\n",
      "Index: 7406, Value: 0.0007092942821693192\n",
      "Index: 2464, Value: 0.0007089904505395024\n",
      "Index: 3578, Value: 0.0007088120653618906\n",
      "Index: 930, Value: 0.000708002617788702\n",
      "Index: 6777, Value: 0.0007078878843602238\n",
      "Index: 2484, Value: 0.0007045990553899923\n",
      "Index: 4944, Value: 0.0007007810591846452\n",
      "Index: 1197, Value: 0.0006994816492666332\n",
      "Index: 3221, Value: 0.0006987253983041838\n",
      "Index: 2041, Value: 0.0006982569375722984\n",
      "Index: 7579, Value: 0.0006975476267000939\n",
      "Index: 6787, Value: 0.0006972322184974253\n",
      "Index: 6530, Value: 0.0006964627253017163\n",
      "Index: 8112, Value: 0.0006961736303552945\n",
      "Index: 6005, Value: 0.000695803293652492\n",
      "Index: 6190, Value: 0.0006955241867884879\n",
      "Index: 5655, Value: 0.0006948295375581998\n",
      "Index: 251, Value: 0.0006937759432871052\n",
      "Index: 3951, Value: 0.0006929348363573946\n",
      "Index: 8018, Value: 0.0006923885742204046\n",
      "Index: 233, Value: 0.0006917479212756467\n",
      "Index: 2589, Value: 0.0006912252321428883\n",
      "Index: 5996, Value: 0.0006911235633472936\n",
      "Index: 482, Value: 0.0006908267232700543\n",
      "Index: 972, Value: 0.0006900990428581179\n",
      "Index: 7499, Value: 0.0006863479935488292\n",
      "Index: 7442, Value: 0.0006860297505491399\n",
      "Index: 1173, Value: 0.0006855662798029934\n",
      "Index: 2369, Value: 0.0006849826076478031\n",
      "Index: 6315, Value: 0.0006833085543359093\n",
      "Index: 5129, Value: 0.0006831063096074902\n",
      "Index: 7784, Value: 0.0006828967351106185\n",
      "Index: 5998, Value: 0.0006826843642763969\n",
      "Index: 4692, Value: 0.00068247636743583\n",
      "Index: 4255, Value: 0.0006824372471686086\n",
      "Index: 6692, Value: 0.0006820009009692969\n",
      "Index: 4832, Value: 0.0006816214190243353\n",
      "Index: 5275, Value: 0.0006798669096450452\n",
      "Index: 5376, Value: 0.0006792710853897303\n",
      "Index: 2232, Value: 0.0006772922181264855\n",
      "Index: 6928, Value: 0.0006765547461563114\n",
      "Index: 260, Value: 0.0006752840006489069\n",
      "Index: 1677, Value: 0.000675179589202962\n",
      "Index: 6847, Value: 0.0006735968311919974\n",
      "Index: 6883, Value: 0.0006731140510828921\n",
      "Index: 7702, Value: 0.0006730776389957352\n",
      "Index: 1798, Value: 0.0006722509491725339\n",
      "Index: 4681, Value: 0.0006712059416513804\n",
      "Index: 2664, Value: 0.0006704377117612958\n"
     ]
    }
   ],
   "source": [
    "top_indices = np.argsort(rank_new)[::-1][:100] #找出前100个最大值的索引\n",
    "top_values = rank_new[top_indices]\n",
    "\n",
    "for i in range(100):\n",
    "    print(f\"Index: {top_indices[i] + 1}, Value: {top_values[i]}\")\n",
    "\n",
    "with open(out_path, 'w') as f:\n",
    "    for i in range(100):\n",
    "        f.write(f\"{top_indices[i] + 1} {top_values[i]}\\n\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
